Interrupts and the role of the stack

We have covered the use of the stack in high level programming languages as an abstract data type to store and retrieve data. If the repl.it link for Forth is not available, you can also do the basics using the site here.

Stack and RPN tasksDownload
Forth Cheat SheetDownload

It also plays an important role in tree traversal in the evaluation of expressions through postfix notation (also known as Reverse Polish Notation), and also in algorithms that make use of backtracking. Less clear up to now has been its role as a low level mechanism for preserving CPU register values during an interrupt and for use in sending and retrieving values when calling subroutines. We will look at this now.

The Hardware Stack

The stack is so fundamental to program development, that most CPUs have hardware dedicated to implementing a stack, and special instructions to allow the most typical stack operations. A special register called the Stack Pointer (SP) is maintained by the CPU, and updated as the stack is being used. We can see how it works using the most complex version of LMC developed by Peter Higginson.

Activity 1

Open the ARM version of LMC, and study the panels in the display. Note the stack pointer SP, the step button which allows us to run one instruction at a time, and the page field which allows us to jump to a different range of memory locations. Each location holds 4 bytes, so each line is 16 bytes long. Currently displayed is page 0, so we see locations 00000 to 001ff.

MOV R0, #1
PUSH {R0}
MOV R0, #2
PUSH {R0}
POP {R0}
POP {R0}
  • Go into edit mode in the left hand window of LMC
  • Copy and paste the text above into the editor
  • Click submit
  • Step through each instruction by clicking the step button and observe the effect on the stack pointer register SP.
  • Click on the STOP button in LMC, then click the CLEAR button on the bottom left of the screen.
  • Now type FFF into the page field so that now you are looking at memory locations FFFE0 – FFFFF
  • Step through the instructions again, this time looking at the last two locations in memory and the value of registers R0, and SP

Explanation

What we are seeing here is a hardware stack in operation, as the values 1 and 2 are loaded into a CPU register and then each one is pushed onto the stack. The stack in this CPU initially points to the highest memory location. Each time an item is pushed on the stack, the stack pointer is decremented by one, and the item is placed at that memory location.

When the simulator first loads, the value of SP is 100000. Hence the first value is placed at memory location 100000 – 1 = FFFFF. Pushing another value will make the same thing happen again, so the next item pushed will go to memory location FFFFF – 1 = FFFFE. When popping, the stack is a LIFO so the most recent value pushed onto the stack is retrieved first, and then the stack pointer is incremented. So you’ll see the value 2 retrieved into R0, then 1.

Interrupts

Interrupts are hardware signals received by the CPU which stop the CPU from doing whatever it is currently doing, to perform some other task. This interrupt request signal is part of the control bus. In a desktop computer, there will typically be interrupts generated when a key is pressed, or when data is being received from or sent to a sound card or graphics card. Interrupts are also used to provide task scheduling in multi tasking operating systems.

The interrupts cause execution to continue from a different location in memory, and they will continue until the code that is being run (called an Interrupt Service Routine or ISR) has completed. The CPU then continues execution on from where it was before the interrupt happened.

In terms of the Fetch-Decode-Execute (FDE) cycle, the CPU will always complete execution of the current instruction before checking for an interrupt request. Then the whole cycle starting from Fetch repeats.

Sounds great, but what has that got to do with the stack? Well the stack plays a crucial role in preserving the state the CPU was in before it was interrupted. The PC register is automatically saved onto the stack first, so that when the ISR has finished, the CPU knows which address to return to and therefore can carry on execution from where it was interrupted.

The programmer can also use the stack inside the ISR to preserve the value of any registers that are going to be used. Say they want to make use of register R1 for some reason. Pushing R1 onto the stack on entry to the ISR saves a copy of its value. The ISR might then overwrite the value currently in the R1 register as part of doing whatever it needs to do. When the ISR is done, the value of R1 can be popped back off the stack and the register will now be back to its previous state.

If we don’t do this, then we have potentially corrupted the value of R1 by interrupting, and may have introduced a bug into our program.

Activity 2

The demo code below will count from 1 to 12, 12 times and then start again. If you click the lightning bolt icon, you will interrupt the CPU. Nothing seems to happen but if you stop the CPU you will see that the value at testLocation (FFFFFF) has been overwritten with 1.

      MOV R0,#isr1
      STR R0,.PinISR
      MOV R0,#1
      STR R0,.PinMask
      STR R0,.InterruptRegister
start: mov r0,#0
outer: add r0,r0,#1
      mov r1,#0
inner: add r1,r1,#1
      cmp r1,#12
      str r0,.WriteUnsignedNum
      bne inner
      cmp r0,#12
      bne outer
      b start
isr1: push {r0}
      mov r0,#1
      str r0,testLocation
      pop {r0}
      rfe
testLocation: .WORD 0xffffffff

Activity 3

  • Edit the program above so that the ISR no longer pushes the value of R0 onto the stack, nor does it pop R0 back off the stack
  • Single step through the code at least 12 times around the loop until the output starts to show the number 2
  • Click the interrupt lightning bolt icon
  • Carry on single stepping
  • What do you notice happens to the count?
  • Why is this happening?
  • What does it tell you about the need for register preservation in ISRs and the use of the stack?

The stack and function calls

The stack can also be used to send and receive values between assembly language subroutines. High level languages may also use the stack in the same way:

  • Arguments to be passed to a function are placed on the stack when it is called
  • Return value(s) are placed on the stack when the function has finished execution
  • Execution continues on from where the function was first called

Because a function might use local variables, which are often stored in registers, these might also be preserved on the stack when one function calls another. All these values associated with a single function call, are gathered together and dumped onto the stack as one logical entity called a frame. When a program crashes, we can sometimes deduce what happened by looking at the stack and seeing what is contained in the various frames.

A stack frame collects together important data as a single unit, which is put onto the stack when one subroutine calls another.

Challenge Activity

Use a subroutine to receive two arguments on the stack, which are two integer values. The subroutine should add the two integers together and place the result on the stack before returning to the calling code.

Hint: BL is the mnemonic to call a subroutine, and RET is the keyword to return from a subroutine. A full manual for LMC can be found here. Subroutines are on page 47-48.

Knowledge Check

  • Name 3 ways we can use the ADT stack
  • What is the hardware stack?
  • Why do you need to preserve register values using the stack?
  • What other use might the hardware stack have for a programmer?
  • What is the stack frame, and why is it useful to debug system crashes?