4 ms·

The concept of the stack is built into the CPU? That's news to me... I mean, I'm not a hardware guy so I guess I could have been misinformed, but I thought it w

by skj 13y ago

The concept of the stack is built into the CPU? That's news to me... I mean, I'm not a hardware guy so I guess I could have been misinformed, but I thought it was something the OS managed as a reserved chunk of main memory (like the heap). Registers are built into the CPU, but that's a different thing than the stack.

a-priori 13y ago
In the x86 family anyway, it's kinda-sorta 'built in'. It is possible to avoid using the stack -- it's done in interrupt handlers which do not have a stack of their own and must avoid clobbering it -- but most code uses it fairly frequently and there are many auxiliary instructions that push and pop from the stack. In addition to some explicit stack-related instructions like PUSH/POP, PUSHF/POPF, PUSHA/POPA, PUSHAD/POPAD and many others, certain other operations assume you have a valid stack and act on it. For example, the CALL function (used to call a procedure/function) will push a return address to the stack, and RET (used to return to the caller at the end of a procedure/method) will pop the return address to the stack and jump to it. These instructions are fairly essential to the function calling conventions for typical code, enough that it's reasonable to say that the concept of the stack is 'built into' x86 processors. Partly this is because the x86 processor is a beast with an instruction for everything. Other more RISCy architectures tend to not bake in the stack, and instead you use any general-purpose register as a stack pointer and manipulate it manually with regular instructions. http://en.wikipedia.org/wiki/X86_instruction_listings http://en.wikipedia.org/wiki/X86_instruction_listings
- joezydeco 13y ago
  Lots of smaller microprocessors live by the stack. Aside from the typical JSR/RET stuff with pushing the program counter, you can also do very lightweight programming tricks with the stack pointer. For example, you can pass arguments to an assembly subroutine by putting the data right after the JSR call. The called subroutine pulls the args by manipulating the stack pointer and the return will jump PC after the argument date. You can also use stack pointer to briefly allocate a small amount of memory for scratch inside a routine instead of allocating heap or using globals. This is a big help on small micros where you might get a scratch register or two normally but now you need 4 or 8 bytes for a quick piece of work.
coin 13y ago
Is this part of basic Computer Science curriculum now adays?
- mtdewcmu 13y ago
  I had to do a little bit with assembly language for a core course and learn a little about hardware. So probably yes, at least at some places.
haberman 13y ago
Yes I think it's better to say this in a more limited way: certain CPU instructions such as push, pop, and call manipulate the stack pointer register in a way that assumes common stack conventions. One interesting thing is that the implementation of these instructions do specify the question of whether the stack grows up or down. On x86 these instructions subtract from rsp when they want to grow the stack, ergo on x86 the stack grows down.
mtdewcmu 13y ago
I don't know about all architectures, but I took a peek at ARM and it has a stack pointer register and built-in instructions that use the stack. So that's Intel and at least one RISC cpu that assume a stack. Of course, you can probably write programs with no stack, and never use the stack instructions, or even put them to other purposes. But there are probably performance reasons for having instructions that automatically manipulate a function call stack, and it would be hard to live without any functions.
- e12e 13y ago
  It would quickly become painful to only transfer execution with JMP-instructions -- you'd need some way to keep track of either how to return, or where you'd be going next (this is exactly equivalent to only using GOTOs for control flow -- and as we know, considered harmful). I suppose on x86 you could create a calling convention where you store a return address in a register or something -- but on 32bit you're already rather short on registers. It would probably be more (if still not really) sensible on amd64. I only see this as viable for rather simple state-machine designs -- but I suppose you could also just generate machine code that read return addresses from an area of memory or something ("the tape" in Turing parlance).

by skj 13y ago

a-priori 13y ago

In the x86 family anyway, it's kinda-sorta 'built in'. It is possible to avoid using the stack -- it's done in interrupt handlers which do not have a stack of their own and must avoid clobbering it -- but most code uses it fairly frequently and there are many auxiliary instructions that push and pop from the stack. In addition to some explicit stack-related instructions like PUSH/POP, PUSHF/POPF, PUSHA/POPA, PUSHAD/POPAD and many others, certain other operations assume you have a valid stack and act on it. For example, the CALL function (used to call a procedure/function) will push a return address to the stack, and RET (used to return to the caller at the end of a procedure/method) will pop the return address to the stack and jump to it. These instructions are fairly essential to the function calling conventions for typical code, enough that it's reasonable to say that the concept of the stack is 'built into' x86 processors. Partly this is because the x86 processor is a beast with an instruction for everything. Other more RISCy architectures tend to not bake in the stack, and instead you use any general-purpose register as a stack pointer and manipulate it manually with regular instructions. http://en.wikipedia.org/wiki/X86_instruction_listings http://en.wikipedia.org/wiki/X86_instruction_listings

joezydeco 13y ago
Lots of smaller microprocessors live by the stack. Aside from the typical JSR/RET stuff with pushing the program counter, you can also do very lightweight programming tricks with the stack pointer. For example, you can pass arguments to an assembly subroutine by putting the data right after the JSR call. The called subroutine pulls the args by manipulating the stack pointer and the return will jump PC after the argument date. You can also use stack pointer to briefly allocate a small amount of memory for scratch inside a routine instead of allocating heap or using globals. This is a big help on small micros where you might get a scratch register or two normally but now you need 4 or 8 bytes for a quick piece of work.

coin 13y ago

Is this part of basic Computer Science curriculum now adays?

mtdewcmu 13y ago
I had to do a little bit with assembly language for a core course and learn a little about hardware. So probably yes, at least at some places.

haberman 13y ago

Yes I think it's better to say this in a more limited way: certain CPU instructions such as push, pop, and call manipulate the stack pointer register in a way that assumes common stack conventions. One interesting thing is that the implementation of these instructions do specify the question of whether the stack grows up or down. On x86 these instructions subtract from rsp when they want to grow the stack, ergo on x86 the stack grows down.

mtdewcmu 13y ago

I don't know about all architectures, but I took a peek at ARM and it has a stack pointer register and built-in instructions that use the stack. So that's Intel and at least one RISC cpu that assume a stack. Of course, you can probably write programs with no stack, and never use the stack instructions, or even put them to other purposes. But there are probably performance reasons for having instructions that automatically manipulate a function call stack, and it would be hard to live without any functions.

e12e 13y ago
It would quickly become painful to only transfer execution with JMP-instructions -- you'd need some way to keep track of either how to return, or where you'd be going next (this is exactly equivalent to only using GOTOs for control flow -- and as we know, considered harmful). I suppose on x86 you could create a calling convention where you store a return address in a register or something -- but on 32bit you're already rather short on registers. It would probably be more (if still not really) sensible on amd64. I only see this as viable for rather simple state-machine designs -- but I suppose you could also just generate machine code that read return addresses from an area of memory or something ("the tape" in Turing parlance).