-3

What will be the instruction sequence that implements PUSH R4?

A: SUB SP, SP, #4 STR R4, [SP, #0]

B: STR R4, [SP, #0] SUB SP, SP, #4

C: ADD SP, SP, #4 STR R4, [SP, #0]

D: STR R4, [SP, #0] ADD SP, SP, #4

E: All of the above are possible

The correct answer is E, but I don't quite follow.

For A, SP would point at the current stack value, and then the SUB command would move it to a new empty place in the stack where R4 is then stored.

For B, R4 is stored at the current place in the stack and then the stack pointer moves to an empty space. Wouldn't this overwrite the current value in the stack when R4 is written?

For C and D, wouldn't the ADD move it back from the stack? So in C, R4 overwrites a value, and in D, the next value pushed onto the stack would overwrite R4?

stumped
  • 145
  • 2
  • 7
  • 1
    This is, of course, only answerable in the context of a specific architecture **which you have neglected to identify**. For example, it is entirely possible to build a stack which grows up or down in memory, and to have a machine which addresses memory in units of register width or in other units, for example byte addressing of a 32-bit or 64-bit machine. Until you specify an architecture by name or details, this question does not belong here. – Chris Stratton Mar 18 '17 at 23:25
  • That context was not given to me. I'm sorry for not already understanding more – stumped Mar 18 '17 at 23:40
  • Essentially the point is that the question is defective, and answer choice E can be argued to come closest to recognizing that. Though it's still a bad question - these are possibilities in distinct designs, but not really in the same design. And there are many other possibilities unmentioned. – Chris Stratton Mar 18 '17 at 23:43

2 Answers2

6

These instruction sequences are not equivalent, they are 4 different ways of implementing stacks.

  • A is a top-down stack where the stack pointer addresses the most recent value.
  • B is a top-down stack where the stack pointer addresses the next insertion point
  • C is a bottom-up stack where the stack pointer addresses the most recent value
  • D is a bottom-up stack where the stack pointer addresses the next insertion point

All of them are valid ways for a CPU to implement a stack, and it would be up to the micro-architecture choice of the CPU, or the OS calling convention if the CPU doesn't have explicit stack instructions.

Traditionally, CPU stacks are top-down (stack starts at a high address in memory and grows down). The reason for this as I understand is primarily due to early CPUs with small address space and no virtual memory, it is convenient to have the stack and heap start at opposite ends of memory and grow to the middle. It was usually easier to do this with the stack than the heap. Now, with 64 bit address space and virtual memory, I doubt it makes much difference, but AFAIK, growing down is still the most common choice.

Evan
  • 2,449
  • 10
  • 17
0

All of the above options are valid ways of implementing a stack, but they are not equivalent. The correct option would depend on the specific architecture. For example, in ARM architecture, only the first option would work, since ARM implements a top-down stack where the stack pointer addresses the value most recently pushed. However, the other options may work for different architectures that may implement the stack differently.

AJT
  • 1