The next few segments have a lot of in-lecture questions, with only a few new concepts. We'll decipher and comment an assembly translation of a simple C program, in order to reinforce the ideas already presented thus far.
Prg5.c is the C program in question. Take a minute to read and understand it. As you can see, it inputs three integers, and prints back the maximum of the three. It calls maxOf3 to do this, and that function in turn calls max which returns the max of just two integers. Much of the point of Prg5.c is to generate a couple of stack frames, thus the odd function design.
Prg5FromC.s has the result of a gcc -S Prg5.c -o Prg5FromC.s command. (You may get a slightly different version if you run that command, due to different gcc versions or other variables.) Prg5FromC.s has the usual surfeit of assembly directives, which are trimmed down to produce Prg5.s, which we'll analyze.
Let's start with the maxOf3 function, on line 29. Like rangeSum from Prg4.s this function starts by building its stack frame. But, it uses a new assembly instruction to do so.
In Prg4.s, rangeSum pushed fp and lr onto the stack via two str instructions:
str lr, [sp, #-4]! @ Save lr to stack str fp, [sp, #-4]! @ Save fp to stack
But maxOf3 uses the single instruction stmfd sp!, {fp, lr}. This pushes both fp and lr onto the stack, and adjusts sp as it does so.
Pushing one or more registers onto the RTS is such a common action (pretty much the start of every function call) that it's common for ISAs to have specialized instructions for it. The ARM instruction is stmfd. It takes a curly-braced list of registers, which may include any or all of the 16 registers, and pushes them onto the RTS, moving backward in address as it grows the RTS "upward". The ! after sp makes sp decrease along with this process, just as it does for the str lr, [sp, #-4]! The sp register ends up holding the address of the last thing pushed onto the stack, or in other words, pointing to the new top of stack.
stmfd pushes the registers in number-order, i.e. r0 before r1, or lr (r14) before pc (r15). This happens no matter what order they appear in the braces. Always list the registers in ascending order of register number; the assembler will warn you if you don't.
Does the stmfd sp!, {fp, lr} instruction do exactly the same thing as the two str instructions above?
Answer 1
stmfd puts fp on the stack first, below the lr which is second since fp is r11 while lr is r14. The two strs put them in the opposite order.
In the prior code example, we put fp above lr, because it was easier to understand the code that way when we built the frame with ldr instructions. But the normal order is what is done by stmfd, with fp at the very bottom of the stack frame, and lr just above it.
All our stack frames from now on will follow this new order.
What if we did these two instructions? Would they have the same effect as `stmfd sp!, {fp, lr}? If not, how would they differ?
str fp, [sp], #-4 @ Save fp to stack str lr, [sp], #-4 @ Save lr to stack
Answer 2
All our code examples assume that sp points to the top word of the RTS, not to the empty space above it. But an equally valid approach would be to always point sp to the next empty space above the RTS. Then we'd want behavior like those two str instructions in Question 2.
A stack design in which the TOS pointer points to the top filled spot in the stack is called a full stack. A stack design in which the TOS pointer points to the next empty spot is an empty stack. The ARM ISA offers a stmed instruction that works just like stmfd, but post-increments sp to implement an empty stack. "stmfd" stands for "store multiple full descending", and "stmed" stands for "store multiple empty descending."
Both stmfd and stmed are "descending" because the address in sp decreases as the stack is filled -- the stack grows backward in memory. One might imagine a different RTS design with addresses increasing as the stack grew. For that design, in full and empty variations, there are 'stmfa' and 'stmea' instructions ("store multiple full ascending" and "store multiple empty ascending").
All four variations stmfd, stmed, stmfa and stmea produce the same basic machine language instruction, with two option bits in it to produce ascending/descending, or empty/full behavior. But did we really need four variations?
Yes, as a matter of fact. These instructions reflect the importance of RTS design, and the fact that every programming language has slightly different calling conventions (recall that term from earlier) for the RTS, including direction of RTS growth and full/empty behavior. A good ISA accommodates all the likely variations.
And, just in case all those options aren't enough, the use of stmfd sp!, ... is so common across many languages that ARM assembly offers a pseudoinstruction that's a bit shorter. As the line 29 comment indicates, push {fp, lr} is an abbreviation for stmfd sp!, {fp, lr}.
The bottom of our new stack frame is the location at which the old fp was stored, and sp points to the lr. So, line 30 correctly changes fp to point to bottom of the new stack frame.
Explain how adding 4 to sp gives us the address of the bottom of the frame.
Answer 3
Line 31 subtracts 3 words (12 bytes) from sp as the diagram shows, effectively creating three additional words of space in the stack frame. Lines 32-34 then fill those words with the three parameters a, b, and c, which are passed in registers r0, r1, and r2, per the calling convention. These appear on the stack as shown in the diagram.
Rewrite lines 32-34 to use sp instead of fp.
Answer 4
As we said in the earlier examples, when fp is used (it's not always) the stack frame can be accessed either via fp or sp, but fp is preferred by the compiler because in some more complex cases the sp may change a little during the function execution.
What are lines 35-37 doing? Explain each instruction exactly.
Answer 5
max, by loading a and b into r0 and r1 as parameters for max, and then doing a bl to max. In the next segment, we'll look at how max adds its own stack frame to the RTS.