In this segment we'll look more closely at how stack frames are created, used, and destroyed. We'll build a detailed, word-by-word diagram of the RTS.
In the last segment we talked about the TOS, but it was a general idea, referring to the entire top stack frame. In practice, the TOS frame is tracked by a designated register pointing to an exact address. In our examples, that will be the address of the byte at the very top of the stack, as indicated in the diagram, and it will be held in R13, which is a specially designated register like R15. R13 is the stack pointer or sp.
In our initial detailed diagram, we show sp pointing to the top of the main stack frame.
Stack frames are so important that we'll also designate another register, sp and fp bracket the TOS stack frame.
A second register pointing to the TOS stack frame may seem redundant, and in some cases we'll use just sp and not fp, but for reasons we'll discuss later, two registers are often useful.
And at this point we should talk about what we mean by "up" in the RTS. Which way in memory is the RTS growing when we add a new stack frame?
It's growing toward lower addresses -- the address in sp decreases as the RTS grows. This may seem odd, but it's a common convention, and it makes it natural to draw memory diagrams in which memory addresses increase from top to bottom, and the RTS moves upward from bottom to top, in decreasing memory address order.
The prior segment explained that we cannot assume that local variables and parameters are at some fixed memory location because we don't know how many stack frames are below the TOS and thus don't know at exactly which memory address the TOS will be. So how do we write ldr and str instructions to get local data?
We use fp or sp as address registers, and offset from them into the TOS stack frame.
Each local variable and parameter is at a known position within its stack frame. For instance, let's assume in this diagram that fp points to the word (4 bytes) just below total in the main stack frame. To load total into say r2, we can write
ldr r2, [fp, #-4]
The location of the stack frame may vary depending on prior function calls, but fp will always point to its bottom, and thus total will always be loadable by offsetting -4 bytes from fp.
All accesses of local state use either sp or fp as address registers, and offset from them to get the desired data within the stack frame.
Now that we know how fp and sp are used, let's look at some code in Prg4.s.
Let's start with the call of rangeSum from main on lines 44-47. A function call in assembly generally takes several instructions, and follows a calling convention that determines how to pass parameters, set up a stack frame for the called function, and get any return value.
There are various methods for passing parameters in assembly, but the simplest is to use designated registers when there are only a few parameters and they are simple values like integers. ARM assembly reserves registers r0 through r3 for parameters. These registers can be used for temporary computations between function calls, as our earlier examples have done. But when you call a function, they must contain parameter values. And the function assumes that it may use them as temporary or scratch registers for its own purposes, trashing any data you might have in them.
That's why lines 44 and 45 put values 10 and 20 into r0 and r1. These two registers will contain values for parameters lo and hi.
Line 46 branches to the start of rangeSum. It's like any other branch instruction, but with one added detail. When we call a function, we'll need to return from it, jumping back to the next instruction in the caller (line 47 in our case). The bl or "branch with link" instruction jumps to the function, but also saves the location of the next instruction in r14: the link register or lr. Function rangeSum will use that value to jump back to line 47 when it's done.
We now have four specially designated and named registers:
After line 46 branches to the start of rangeSum, lines 4-11 set up the new stack frame for rangeSum. Setting up a stack frame is generally the job of the function, not the caller.
At line 4, we may assume that:
sp points to the top of the stack frame for mainfp points to the bottom of main's stack framelr points to the place to return when we're doner0 and r1 have values for lo and hiOur tasks are:
lr, so we know where to jump backfp, and change fp to point to the base of our new stack framelo and hi, and local variable sumlo, hi, and sum.Let's see how lines 4-11 accomplish this.
lr at a location 4 bytes "above" (4 bytes lower in memory) the top of the existing main stack frame. This is the first entry in our new stack frame. And it leaves sp pointing to the new entry because of the !.fp value. Now we have two words on the stack frame, and sp points to the top of it.fp to point to the old fp value in the new stack frame. For the moment, sp and fp point the same place.sp by 3 words, effectively adding 3 words of space to the stack frame. Now we have fp pointing almost to the bottom of the stack frame, with the space for local variables and parameters above it (lower in memory). Sum is immediately above it, next is lo, and then hi.fp, respectively. This shows that those locations contain lo and hi, respectively, since r0 and r1 contain those parameter values. As mentioned before, we're using fp as an address register, and offsetting from it.fp as an address register to store the 0 at the location just above fp, showing that that's the location of sum, since the C code initializes sum to 0.Now we have a completed stack frame. Note that the bottom of the frame has information needed when we return from the function: the return location and the old frame pointer. And the top of the frame holds local state: parameters and local variables.
The code that follows uses [fp, #-4] for sum, [fp, #-8] for lo, and [fp, #-12] for hi. All local state is obtained via offset from fp, so no matter where the stack frame actually is in memory, we'll get the right locations as long as fp is pointing to the bottom of the frame.
fp, instead using sp.
Answer 1
The next segment will cover the remainder of rangeSum, including the process of undoing the stack frame and returning.