In this segment we'll examine the first half of the assembly for main from the Primes.c program. This will again be a "guided tour", with ILQs asking you to think through the code on your own as much as you can, and comment as you go.
The first 7 instructions in main set up the stack frame and initialize some of the locals, implementing these lines from Primes.c:
const int numsToTest = 320; unsigned primeSet[10]; // Space for 320 bits int totalPrimes = 0, toTest, idx;
It's the most complex frame setup we've seen so far. Analyze it, and then answer the question below.
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #56
mov r3, #320
str r3, [fp, #-20]
mov r3, #0
str r3, [fp, #-8]
Question 1 How many bytes of local storage are there in the frame? Why that much? What are they used for? Can you determine the location of any of the local variables relative to fp? What do you think occupies the top of the frame? Are any of the bytes left unused, as has been the case in some earlier stack frames?
Answer 1
primeSet, and another 16 bytes for the four int variables. There is no unused space. From the stack frame code, it looks like numsToTest is at offset -20, since we're setting that to 320. (And an aside here. We've said that 255 was the maximum constant allowed in a mov, but I alluded to the fact that certain larger constants are also allowed. This is such a case: 320 is permitted. More details on that to come in the topic on the ISA design.)
And, totalPrimes is at offset -8 since we're setting that to 0. This suggests that toTest and idx are at -12 and -16, though we can't tell which is which till later in the code. And the fact that the int locals are all at the bottom of the frame suggests that the 40 bytes at the top of the frame are for array primeSet.
Question 2
Draw a diagram of the stack frame, from the bottom to the top. And, given the fact that array elements must go in increasing memory order, where exactly in that frame are primeSet[0] and primeSet[9]?
Answer 2
Next, let's look at the machine language for the first loop:
for (idx = 0; idx < 10; idx++)
primeSet[idx] = 0;
Question 3 What assembly instructions implement this loop? Which instructions do the initializer, which do the incrementer, and which do the test? (Recall from prior examples that the loop test may at the bottom of the loop.) And don't try to decipher the loop body at this point. Just identify it; we'll decipher it in a bit.
Answer 3
idx, which is at offset -16, and line 23 jumps down to the test, which is on lines 35-37. The incrementer is on lines 31-33, just after the body on lines 25-30.
A brief note on the test:
ldr r3, [fp, #-16]
cmp r3, #9
ble .L3
This does an idx <= 9 test, which is logically the same as idx < 10. Wherever possible, the compiler prefers smaller constants since the range of constants is limited.
The loop body, implementing primeSet[idx] = 0, needs careful discussion:
ldr r3, [fp, #-16]
mov r3, r3, asl #2
sub r2, fp, #4
add r3, r2, r3
mov r2, #0
str r2, [r3, #-56]
Question 4
What expression do the first two instructions compute, and leave in r3? Recall that idx is at offset -16. Write your expression using multiplication, not shift. Why would we want that multiplication?
Answer 4
idx * 4 into r3. This is the offset, in bytes, from the start of primeSet to get to primeSet[idx], since each element of primeSet is four bytes.
So now r3 holds the byte offset into primeSet. The next four instructions put a zero in primeSet[idx], but they do it in an odd way.
Question 5
Assuming primeSet starts at the top of the stack frame, at what offset from fp is its first element? Why?
Answer 5
With this in mind, it's easier to see how those four lines work. The sub subtracts just 4 bytes from fp leaving the result in r2, the add adds in the computed offset from r3, and the str offsets another -56 offset to r3, arriving at an address of fp - 60 + idx*4, which is the location of the desired element of primeSet. The str stores a zero there.
Question 6
Rewrite those four lines so the str needs no offset.
Answer 6
sub r2, fp, #60
add r3, r2, r3
mov r2, #0
str r2, [r3]
This sets r2 to the start of primeSet, adds in the byte offset from r3, and just uses the total in r3 as the address. This is intuitively simpler, but has the disadvantage of requiring a larger constant (#60). If the compiler was able to reserve the local space by subtracting a constant of at most 255, it wants to access variables in that local space using constants that are no larger. So, it designs the array index in this odd way.
Question 7
As an exercise, write that array operation with just three instructions, and without changing fp.
Answer 7
add r3, fp, r3
mov r2, #0
str r2, [r3, #-60]
But that uses a constant larger than the one originally used to reserve the local space (-56).
Question 8
Now try rewriting it using just three instructions and no constants other than #0. Using sp will help.
Answer 8
add r3, sp, r3
mov r2, #0
str r2, [r3]
In the next segment we'll finish the discussion of main by looking at the assembly for the second loop.